import java.util.*;
public class Solution {
    /*这种题就是求任取k个数的不同种取法：注意如何剪取
    * 另外：一般思路都是先排序然后循环取获得，但要注意剪枝。
    * 为什么不用回溯法：应该与求全排列问题进行区分*/
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        int len = num.length;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(num);

        for (int i = 0; i < len-2; ++i) {
            if (i != 0 && num[i] == num[i-1]) continue; // 剪枝
            for (int j =i+1; j < len-1; ++j) {
                if (j != i+1 && num[j] == num[j-1]) continue;  /*剪枝*/
                for (int k = j+1; k < len; ++k) {
                    if (k != j+1 && num[k] == num[k-1]) continue;  /*剪枝*/
                    int sum = num[i] + num[j] + num[k];

                    if (sum == 0) {
                        ArrayList<Integer> temp = new ArrayList<>();
                        temp.add(num[i]);
                        temp.add(num[j]);
                        temp.add(num[k]);
                        res.add(temp);
                        break;
                    }
                }
            }
        }
        return res;
    }
}